#include <iostream>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <thread>
#include <memory>
#include <vector>

using std::cout;
using std::cin;
using std::cerr;
using namespace std::chrono;
using std::thread;
using std::vector;

const unsigned core_count {thread::hardware_concurrency()};        // 电脑线程数

void break_num(int64_t num);             // 分解这个整数的因数，并计时
int64_t thread_factorize(int64_t num);       // 多线程分解因数
void test_factor(int64_t num, int64_t min, int64_t max, int64_t& result);          // 测试[min, max]之间是否有num的因数

// Qt/C++交流群：972330913
int main(int argc, char** argv)
{
    cout << "请输入要分解的数：";          // 9999996000000319
    int64_t big_num;
    cin >> big_num;
    if (big_num < 2)
        cerr << "必须输入大于2的整数\n";
    else
        break_num(big_num);
    system("pause");
	return 0;
}

void break_num(int64_t num)
{
    auto begin = high_resolution_clock::now();
    int64_t factor {};
    if (num < core_count*core_count) {
        for (int64_t i{2}; i<=static_cast<int64_t>(sqrt(num)); ++i)
            if (num%i == 0) {
                factor = i;
                break;
            }
    }
    else
        factor = thread_factorize(num);
    auto end = high_resolution_clock::now();
    if (factor == 0)
        cout << "该数是一个素数\n";
    else
        cout << num << " == " << factor << " * " << num/factor << '\n';
    cout << "用时：" << duration_cast<milliseconds>(end-begin).count() << "ms\n";
}

int64_t thread_factorize(int64_t num)
{
    vector<thread> threads;
    int64_t result {};
    int64_t test {static_cast<int64_t>(sqrt(num))-2};
    for (auto i=core_count; i!=0; --i) {
        thread th {test_factor,num,test-test/i+2,test+2,std::ref(result)};
        threads.emplace_back(std::move(th));
        test -= test/i;
    }
    for (auto& th : threads)
        th.join();
    return result;
}

void test_factor(int64_t num, int64_t min, int64_t max, int64_t& result)
{
    for (auto i=min; i<=max; ++i) {
        if (num%i == 0)
            result = i;
        if (result != 0)
            return;
    }
}
